import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-05-27
 * Time: 10:29
 */

/**
 *  并查集
 */
class UnionFindSet{
    public int[] arr;
    public UnionFindSet(int size){
        this.arr = new int[size];
        Arrays.fill(arr, -1);
    }

    /**
     *  添加边
     * @param index1
     * @param index2
     * @return
     */
    public boolean addEdge(int index1, int index2){
        int root1 = findRoot(index1);
        int root2 = findRoot(index2);
        // 构成环了
        if (root1 == root2){
            return false;
        }
        // 没有构成环则合并两个集合
        this.arr[root1] += this.arr[root2];
        // 修改第二个集合的根与第一个集合的根相同
        this.arr[root2] = root1;
        return true;
    }

    /**
     *  找到根节点
     * @param index
     * @return
     */
    public int findRoot(int index){
        while (this.arr[index]  > 0){
            index = this.arr[index];
        }
        return index;
    }
}

class Solution {
    public int[] findRedundantConnection(int[][] edges) {
        int[] ans = new int[2];
        int n = edges.length;
        UnionFindSet ufs = new UnionFindSet(n + 1);
        for (int[] edge: edges) {
            int from = edge[0];
            int to = edge[1];
            // 没有添加成功
            if (!ufs.addEdge(from, to)){
                ans[0] = from;
                ans[1] = to;
            }
        }
        return ans;
    }
}
